home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / plane / _seg_tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  22.0 KB  |  947 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _seg_tree.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. // ------------------------------------------------------------------
  18. //
  19. // full dynamic Segment Trees
  20. //
  21. // Michael Wenzel     (1990)
  22. //
  23. // Implementation as described in
  24. // Kurt Mehlhorn: Data Structures and Algorithms 3
  25. //
  26. // ------------------------------------------------------------------
  27.  
  28.  
  29. #include <LEDA/impl/seg_tree.h>
  30.  
  31. enum left_or_right {left = 0, right = 1};
  32.  
  33. #undef TEST
  34. #undef DUMP
  35.  
  36. #ifdef TEST
  37. #define DPRINT(x) cout << x
  38. #else
  39. #define DPRINT(x)
  40. #endif
  41.  
  42. #ifdef DUMP
  43. #define DDUMP(x) cout << x
  44. #else
  45. #define DDUMP(x)
  46. #endif
  47.  
  48. ostream& operator<<(ostream& s, h_segment& h) 
  49. { 
  50.   s<<"("<<(int)h._x0<<","<<(int)h._x1<<";"<<(int)h._y<<")";
  51.   return s;
  52. }
  53.  
  54. //-------------------------------------------------------------------
  55. // member functions
  56. //-------------------------------------------------------------------
  57.  
  58. int seg_node_tree::cmp(GenPtr x,GenPtr y) const
  59. { return father->seg_cmp((h_segment_p)x,(h_segment_p)y); }
  60.  
  61. // ------------------------------------------------------------
  62. // query
  63. // returns a List of all items it with y0 <= y(it) <= y1
  64.  
  65. list<seg_tree_item> seg_node_tree::query(GenPtr y0, GenPtr y1)
  66. { 
  67.   DPRINT(" query in nodelist\n");
  68.  
  69.   list<seg_tree_item> L;
  70.  
  71.  
  72.   h_segment_p r = father->new_y_h_segment(y0);
  73.   seg_tree_item it = locate(r);
  74.  
  75.   if (it)
  76.   { while ( it!=min() && father->cmp_dim2(key(it)->_y,y0)==0) it = pred(it);
  77.     while ( it && father->cmp_dim2(key(it)->_y,y1)<=0)
  78.     { L.append(it);
  79.       it = succ(it);
  80.      }
  81.    }
  82.  
  83.   delete r;
  84.   return L;
  85. }
  86.  
  87.  
  88. //-------------------------------------------------------------------
  89. // all_items
  90. // returns all items in the nodelist
  91.  
  92. list<seg_tree_item> seg_node_tree::all_items()
  93. {
  94.   list<seg_tree_item> L;
  95.   seg_tree_item z;
  96.  
  97.   forall_seg_tree_items(z,*this)
  98.     L.append(z);
  99.   
  100.   return L;
  101. }
  102.  
  103.  
  104. //-------------------------------------------------------------------
  105.  
  106. Segment_Tree::Segment_Tree() : r(this)  {} 
  107. Segment_Tree::~Segment_Tree() { clear(root); }
  108.  
  109. int Segment_Tree::seg_cmp(h_segment_p p, h_segment_p q)
  110. { int a;
  111.   if (a = cmp_dim2(p->y(), q->y())) return a;
  112.   if (a = cmp_dim1(p->x0(),q->x0())) return a;
  113.   return cmp_dim1(p->x1(), q->x1());
  114. }
  115.  
  116. // ------------------------------------------------------------
  117. // empty
  118. // returns true, iff for all seg_tree_items it in nodelist(it):
  119. //                 key(it) is not a start- or endoordinate of key(it)
  120.  
  121. int Segment_Tree::empty(bb_item it)
  122. {
  123.   DPRINT(" empty of "<<(int)key(it)<<"\n");
  124.   int erg=true;
  125.   seg_tree_item i;
  126.  
  127.   forall_seg_tree_items(i,*info(it))
  128.     if ( (cmp(key(it),x0(i))==0) || (cmp(key(it),x1(i))==0) )
  129.       erg = false;
  130.  
  131.   DPRINT("empty ergibt "<<erg<<"\n");
  132.   return erg;
  133. }   
  134.  
  135. // ------------------------------------------------------------
  136. // lrot() , rrot() , ldrot() , rdrot()
  137. // Rotationen am Knoten p
  138.  
  139. void Segment_Tree::lrot(bb_item p, bb_item q)
  140. {
  141.   bb_item h = p->sohn[right];
  142.  
  143.   DDUMP("lrot "<< (int)key(p)) ; 
  144.     if (q) DDUMP(" Vater " << (int)key(q));
  145.   DDUMP("\n");
  146.  
  147.   p->sohn[right] = h->sohn[left];
  148.   h->sohn[left] = p;
  149.   if (!q)
  150.     root=h;
  151.   else
  152.   { if (cmp(key(h),key(q))>0)
  153.       q->sohn[right]=h;
  154.     else
  155.       q->sohn[left]=h;
  156.   }
  157.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  158.   h->gr=p->groesse()+h->sohn[right]->groesse();
  159.  
  160.                         // update nodelists
  161.  seg_tree_item i;
  162.  
  163.  bb_item re=p->sohn[right];
  164.  bb_item s=p->sohn[left];
  165.  
  166.  seg_node_list help = info(h);
  167.  info(h) = info(p);
  168.  
  169.  info(p) = new seg_node_tree(this);
  170.  
  171.  forall_seg_tree_items(i,*(info(re)))
  172.    if ( ( (!re->blatt()) 
  173.       ||((!start_coord(re,i))&&(!end_coord(re,i))) )
  174.       && ( (!s->blatt())
  175.        ||((!start_coord(s,i))&&(!end_coord(s,i))) ) 
  176.       && (info(s)->member(r.key(i))) )
  177.  
  178.      info(p)->insert(r.key(i));
  179.  
  180.  forall_seg_tree_items(i,*(info(p)))
  181.  { info(re)->del(r.key(i));
  182.    info(s)->del(r.key(i));
  183.  }
  184.  
  185.  forall_seg_tree_items(i,*help)
  186.  { info(re)->insert(r.key(i));
  187.    info(h->sohn[right])->insert(r.key(i));
  188.  } 
  189.  
  190.  delete help;
  191.  
  192. }
  193.  
  194. void Segment_Tree::rrot(bb_item p, bb_item q)
  195. {
  196.   bb_item h = p->sohn[left];
  197.  
  198.   DDUMP("rrot "<< (int)key(p)) ; 
  199.     if (q) DDUMP(" Vater " << (int)key(q));
  200.   DDUMP("\n");
  201.  
  202.   p->sohn[left] = h->sohn[right];
  203.   h->sohn[right] = p;
  204.   if (!q) root=h;
  205.   else
  206.   { if (cmp(key(h),key(q))>0)
  207.       q->sohn[right] = h;
  208.     else
  209.       q->sohn[left] = h; }
  210.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  211.   h->gr=p->groesse()+h->sohn[left]->groesse();
  212.  
  213.                         // update nodelists
  214.  seg_tree_item i;
  215.  
  216.  bb_item re=p->sohn[right];
  217.  bb_item s=p->sohn[left];
  218.  
  219.  seg_node_list help = info(h);
  220.  info(h) = info(p);
  221.  
  222.  info(p) = new seg_node_tree(this);
  223.  /* forall_seg_tree_items(i,*(info(s)))
  224.     if (info(re)->member(r.key(i)))
  225.       info(p)->insert(r.key(i));    */
  226.  
  227.  forall_seg_tree_items(i,*(info(s)))
  228.    if ( ( (!s->blatt()) 
  229.       ||((!start_coord(s,i))&&(!end_coord(s,i))) )
  230.       && ( (!re->blatt())
  231.        ||((!start_coord(re,i))&&(!end_coord(re,i))) ) 
  232.       && (info(re)->member(r.key(i))) )
  233.  
  234.      info(p)->insert(r.key(i));
  235.  
  236.  forall_seg_tree_items(i,*(info(p)))
  237.  { info(re)->del(r.key(i));
  238.    info(s)->del(r.key(i));
  239.  }
  240.  
  241.  forall_seg_tree_items(i,*help)
  242.  { info(s)->insert(r.key(i));
  243.    info(h->sohn[left])->insert(r.key(i));
  244.  } 
  245.  
  246.  delete help;
  247.  
  248. }
  249.  
  250. void Segment_Tree::ldrot(bb_item p, bb_item q)
  251. {
  252.   bb_item h = p->sohn[right];
  253.   bb_item g = h->sohn[left];
  254.  
  255.   DDUMP("ldrot "<< (int)key(p)) ; 
  256.     if (q) DDUMP(" Vater " << (int)key(q));
  257.   DDUMP("\n");
  258.  
  259.   rrot(h,p);
  260.   lrot(p,q);
  261.  
  262.   /*
  263.   p->sohn[right] = g->sohn[left];
  264.   h->sohn[left] =  g->sohn[right];
  265.   g->sohn[left] = p;
  266.   g->sohn[right] = h;
  267.   if (!q) root=g;
  268.   else
  269.   { if (cmp(key(h),key(q))>0)
  270.       q->sohn[right] =g ;
  271.     else 
  272.       q->sohn[left] = g ; }
  273.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  274.   h->gr=h->sohn[left]->groesse()+h->sohn[right]->groesse();
  275.   g->gr=p->groesse()+h->groesse();
  276.                         // update nodelists
  277.   seg_tree_item i;
  278.  
  279.   seg_node_list help = info(g);
  280.   info(g) = info(p);
  281.   info(p) = new seg_node_tree(this);
  282.  
  283.   forall_seg_tree_items(i,*help)
  284.     info(p->sohn[right])->insert(r.key(i));
  285.  
  286.   forall_seg_tree_items(i,*(info(p->sohn[left])))
  287.     if (info(p->sohn[right])->member(r.key(i)))
  288.       info(p)->insert(r.key(i));
  289.  
  290.   forall_seg_tree_items(i,*(info(p)))
  291.   { info(p->sohn[left])->del(r.key(i));
  292.     info(p->sohn[right])->del(r.key(i));
  293.   }
  294.   
  295.   forall_seg_tree_items(i,*(info(h)))
  296.     info(p->sohn[right])->insert(r.key(i));
  297.  
  298.   forall_seg_tree_items(i,*(info(h->sohn[left])))
  299.     if (info(h->sohn[right])->member(r.key(i)))
  300.       info(h)->insert(r.key(i));
  301.  
  302.   seg_node_list help1 = info(h->sohn[right]);
  303.   info(h->sohn[right]) = new seg_node_tree(this);
  304.  
  305.   forall_seg_tree_items(i,*help1)
  306.   { if (!((info(h->sohn[left]))->member(r.key(i))))
  307.       info(h->sohn[right])->insert(r.key(i));
  308.     else
  309.       info(h->sohn[left])->del(r.key(i));
  310.   }
  311.  
  312.   forall_seg_tree_items(i,*help)
  313.     info(h->sohn[left])->insert(r.key(i));
  314.  
  315.   delete help;
  316.   delete help1;
  317. */
  318.    
  319. }
  320.  
  321. void Segment_Tree::rdrot(bb_item p, bb_item q)
  322.  
  323. {
  324.   bb_item h = p->sohn[left];
  325.   bb_item g = h->sohn[right];
  326.  
  327.   DDUMP("rdrot "<< (int)key(p)) ; 
  328.     if (q) DDUMP(" Vater " << (int)key(q));
  329.   DDUMP("\n");
  330.  
  331.   lrot(h,p);
  332.   rrot(p,q);
  333.  
  334. /*  p->sohn[left] = g->sohn[right];
  335.   h->sohn[right] =  g->sohn[left];
  336.   g->sohn[right] = p;
  337.   g->sohn[left] = h;
  338.   if (!q) root=g;
  339.   else
  340.   { if (cmp(key(h),key(q))>0)
  341.       q->sohn[right] =g ;
  342.     else 
  343.       q->sohn[left] = g ; }
  344.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  345.   h->gr=h->sohn[left]->groesse()+h->sohn[right]->groesse();
  346.   g->gr=p->groesse()+h->groesse();
  347.                         // update nodelists
  348.   seg_tree_item i;
  349.  
  350.   seg_node_list help = info(g);
  351.   info(g) = info(p);
  352.   info(p) = new seg_node_tree(this);
  353.  
  354.   forall_seg_tree_items(i,*help)
  355.     info(p->sohn[left])->insert(r.key(i));
  356.  
  357.   forall_seg_tree_items(i,*(info(p->sohn[right])))
  358.     if (info(p->sohn[left])->member(r.key(i)))
  359.       info(p)->insert(r.key(i));
  360.  
  361.   forall_seg_tree_items(i,*(info(p)))
  362.   { info(p->sohn[left])->del(r.key(i));
  363.     info(p->sohn[right])->del(r.key(i));
  364.   }
  365.   
  366.   forall_seg_tree_items(i,*(info(h)))
  367.     info(p->sohn[left])->insert(r.key(i));
  368.  
  369.   forall_seg_tree_items(i,*(info(h->sohn[right])))
  370.     if (info(h->sohn[left])->member(r.key(i)))
  371.       info(h)->insert(r.key(i));
  372.  
  373.   seg_node_list help1 = info(h->sohn[left]);
  374.   info(h->sohn[left]) = new seg_node_tree(this);
  375.  
  376.   forall_seg_tree_items(i,*help1)
  377.   { if (!((info(h->sohn[right]))->member(r.key(i))))
  378.       info(h->sohn[left])->insert(r.key(i));
  379.     else
  380.       info(h->sohn[right])->del(r.key(i));
  381.   }
  382.  
  383.   forall_seg_tree_items(i,*help)
  384.     info(h->sohn[right])->insert(r.key(i));
  385.  
  386.   delete help;
  387.   delete help1;
  388. */
  389.    
  390. }
  391.  
  392.  
  393. //-------------------------------------------------------------------
  394. // insert
  395. // insert a segment into a Segment_tree:             
  396. // - insert x-coordinates in main tree (bb-alpha) 
  397. //          and rotate (if necessary)
  398. // - insert segment on nodes 
  399. //          immediately below the paths to x-coordinates
  400. // - insert segment into the tree of all segments
  401.  
  402. seg_tree_item Segment_Tree::insert(GenPtr x0, GenPtr x1, GenPtr y, GenPtr inf)
  403.  
  404. {
  405.   DPRINT(" insert segment " << (int)x0 << " " << (int)x1 << " " << (int)y << " in main tree \n" );
  406.  
  407.   seg_tree_item inserted,j;
  408.  
  409.   if (!(cmp(x0,x1)))                         // empty segment
  410.     return 0;
  411.  
  412.   copy_dim1(x0);
  413.   copy_dim1(x1);
  414.   copy_dim2(y);
  415.   copy_info(inf);
  416.  
  417.   h_segment_p i = new h_segment(x0,x1,y,inf);
  418.  
  419.   if (inserted=r.lookup(i)) 
  420.   { delete i;
  421.     r.info(inserted)=inf;
  422.     return inserted;
  423.   }
  424.  
  425.   bb_item t,father,p;
  426.   bb_item start,end;
  427.   seg_node_list h;
  428.  
  429.                 // insert start_coordinate
  430.  
  431.   if (!(start=bb_tree::lookup(x0)))        // new coordinate
  432.   { h=new seg_node_tree(this);
  433.     start = sinsert(x0,h);
  434.     t=start;
  435.   
  436.     if (!st.empty())
  437.     { father = st.pop();         // pop father of leaf and set nodelist
  438.       h=new seg_node_tree(this);
  439.       info(father) = h;
  440.       p = succ(t); 
  441.       if (p)
  442.       { list<seg_tree_item> L;
  443.         L=info(p)->all_items();
  444.         forall(j,L)
  445.       { DDUMP("Item "<<*(r.key(j))<<" in Knoten "<<(int)key(p)<<"\n");
  446.           if (end_coord(p,j))
  447.             info(t)->insert(r.key(j));
  448.           else if (!start_coord(p,j))
  449.                { info(father)->insert(r.key(j));
  450.                  info(p)->del(r.key(j));
  451.                }
  452.         }
  453.       }
  454.     }
  455.     
  456.                                  // rebalancieren
  457.     while (!st.empty())
  458.     { t=st.pop();
  459.       father = st.empty() ? 0 : st.top();
  460.       t->gr++;  
  461.       float i = t->bal();
  462.  
  463.       DDUMP("rebal cur=" << (int)key(t) << " groesse= " << t->groesse() << " bal= " << i << " in main tree\n");
  464.  
  465.       if (i < alpha)
  466.         if (t->sohn[right]->bal()<=d) lrot(t,father);
  467.         else ldrot(t,father);
  468.       else if (i>1-alpha) 
  469.              if (t->sohn[left]->bal() > d ) rrot(t,father);
  470.              else rdrot(t,father);
  471.     }
  472.   }              // start coordinate inserted
  473.  
  474.  
  475.  
  476.                 // insert end_coordinate
  477.  
  478.   if (!(end=bb_tree::lookup(x1)))   // new coordinate
  479.   { h=new seg_node_tree(this);
  480.     end = sinsert(x1,h);
  481.     t=end;
  482.  
  483.     if (!st.empty())
  484.     { father = st.pop();         // pop father of leaf and set nodelist
  485.       h=new seg_node_tree(this);
  486.       info(father) = h;
  487.       p = succ(t); 
  488.       if (p)
  489.       { list<seg_tree_item> L;
  490.         L=info(p)->all_items();
  491.         forall(j,L)
  492.         if (end_coord(p,j))
  493.             info(t)->insert(r.key(j));
  494.           else if (!start_coord(p,j))
  495.                { info(father)->insert(r.key(j));
  496.                  info(p)->del(r.key(j));
  497.                }
  498.       }
  499.     }
  500.  
  501.                                // rebalancieren
  502.     while (!st.empty())
  503.     { t=st.pop();
  504.       father = st.empty() ? 0 : st.top();
  505.       t->gr++;  
  506.       float i = t->bal();
  507.  
  508.       DDUMP("rebal cur=" << (int)key(t) << " groesse= " << t->groesse() << " bal= " << i << " in main tree\n");
  509.  
  510.       if (i < alpha)
  511.         if (t->sohn[right]->bal()<=d) lrot(t,father);
  512.         else ldrot(t,father);
  513.       else if (i>1-alpha) 
  514.              if (t->sohn[left]->bal() > d ) rrot(t,father);
  515.              else rdrot(t,father);
  516.     }
  517.   }              // end coordinate inserted
  518.  
  519.  
  520.      // insert segment into nodelists of leaves of coordinates
  521.  
  522.   info(start)->insert(i);  
  523.   info(end)->insert(i);
  524.  
  525.   p=t=root;
  526.   GenPtr x2,x3;
  527.  
  528.                          // same path
  529.   while (p==t)  // start and end coordinate assigned to different leaves
  530.   { x2=key(p);
  531.     DDUMP(" same path " << (int)x0 << " " << (int)x1 << " " << (int)x2 << "\n");
  532.     if ( cmp(x0,x2)<=0 ) p=p->sohn[left];
  533.       else p=p->sohn[right];
  534.     if ( cmp(x1,x2)<=0 ) t=t->sohn[left];
  535.       else t=t->sohn[right];
  536.   }
  537.                      // now paths to lower and upper part
  538.   while (!p->blatt())                // follow lower path
  539.   { 
  540.     x2=key(p);
  541.     DDUMP(" lower path " << (int)x0 << " " << (int)x2 << "\n");
  542.     if ( cmp(x0,x2)>0 ) 
  543.       p=p->sohn[right];
  544.     else
  545.     { info(p->sohn[right])->insert(i);   // insertion into nodelist
  546.       p=p->sohn[left];
  547.     } 
  548.   }
  549.  
  550.   while (!t->blatt())               // follow upper path
  551.   { 
  552.     x3=key(t);
  553.     DDUMP(" upper path " << (int)x1 << " " << (int)x3 << "\n");
  554.     if ( cmp(x1,x3)<=0 ) 
  555.       t=t->sohn[left];
  556.     else
  557.     { info(t->sohn[left])->insert(i);  // insertion into nodelist
  558.       t=t->sohn[right];
  559.     } 
  560.   }
  561.  
  562. #ifdef DUMP
  563.   print_tree();
  564. #endif
  565.  
  566.   return (r.insert(i)); 
  567. }
  568.  
  569.  
  570. //-------------------------------------------------------------------
  571. // delete
  572. // delete a segment in a Segment_tree:
  573. // - delete segment out of the tree of all segments
  574. // - delete segment on nodes 
  575. //          immediately below the paths to x-coordinates
  576. // - delete x-coordinates in main tree (bb-alpha) 
  577. //          and rotate (if necessary)
  578.  
  579. void Segment_Tree::del(GenPtr x0, GenPtr x1, GenPtr y)
  580.  
  581. {
  582.   DPRINT(" delete segment " << (int)x0 << " " << (int)x1 << " " << (int)y << " in main tree\n");
  583.  
  584.   if (!(cmp(x0,x1)))                         // empty segment
  585.     return ;
  586.  
  587.   bb_item p,q,s,t,father;
  588.   seg_tree_item z;
  589.   seg_node_list help;
  590.   h_segment_p deleted;
  591.   h_segment_p i = new h_segment(x0,x1,y);
  592.  
  593.   if (!(t=r.lookup(i)))          // segment not in tree
  594.   { delete i;
  595.     DDUMP("delete: segment not in tree\n");
  596.     return;
  597.   }
  598.  
  599.   deleted = r.key(t);
  600.   r.del(i);                      // delete in tree of all segments
  601.  
  602.   s=t=root;
  603.   GenPtr x2,x3;
  604.  
  605.                  // delete segment in nodelists
  606.  
  607.   while ((s==t)&&(!s->blatt()))       // same path
  608.   { x2=key(s);
  609.     x3=key(t);
  610.     DDUMP(" same path " << (int)x2 << " groesse " << s->groesse() << "\n");
  611.     if ( cmp(x0,x2)<=0 ) s=s->sohn[left];
  612.       else s=s->sohn[right];
  613.     if ( cmp(x1,x3)<=0 ) t=t->sohn[left];
  614.       else t=t->sohn[right];
  615.   }
  616.                      // now paths to lower and upper part
  617.   while (!s->blatt())                // follow lower path
  618.   { 
  619.     x2=key(s);
  620.     DDUMP(" lower path " << (int)x2 << " groesse " << s->groesse() << "\n");
  621.     if ( cmp(x0,x2)>0 ) 
  622.       s=s->sohn[right];
  623.     else
  624.     { info(s->sohn[right])->del(i);   // delete out of nodelist
  625.       s=s->sohn[left];
  626.     } 
  627.   }
  628.   info(s)->del(i);
  629.  
  630.   while (!t->blatt())               // follow upper path
  631.   { 
  632.     x3=key(t);
  633.     DDUMP(" upper path " << (int)x3 << " groesse " << t->groesse() << "\n");
  634.     if ( cmp(x1,x3)<=0 ) 
  635.       t=t->sohn[left];
  636.     else
  637.     { info(t->sohn[left])->del(i);   // delete out of nodelist
  638.       t=t->sohn[right];
  639.     } 
  640.   }
  641.   info(t)->del(i);
  642.                     // delete in main tree if necessary
  643.  
  644.   if(empty(s))                      // delete item of start coordinate
  645.   {
  646.     sdel(x0);
  647.     if (!st.empty())                // father exists 
  648.     { q = st.pop();                 // pop father of leaf and set nodelist
  649.  
  650.       if (!st.empty())
  651.       { p = st.top();
  652.     if (cmp(key(q),key(p))<=0)  // left son deleted
  653.           p = p->sohn[left];
  654.         else                        // right son deleted
  655.       p = p->sohn[right];
  656.       } 
  657.       else                          // root deleted 
  658.     p = root;
  659.  
  660.                                           // set nodelist
  661.       help = info(p);
  662.       info(p) = info(q);
  663.  
  664.       if (p->blatt())
  665.     forall_seg_tree_items(z,*help)
  666.       if ((start_coord(p,z))||(end_coord(p,z)))
  667.         info(p)->insert(r.key(z));
  668.  
  669.       delete help;
  670.       delete q;
  671.     }
  672.  
  673.     delete info(s);
  674.     delete s;
  675.                                // rebalancieren
  676.     while (!st.empty())
  677.     { p=st.pop();
  678.       father = st.empty() ? 0 : st.top();
  679.       p->gr--;  
  680.       float i = p->bal();
  681.  
  682.       DDUMP("rebal cur=" << (int)key(p) << " groesse= " << p->groesse() << " bal= " << i << " in main tree \n");
  683.  
  684.       if (i < alpha)
  685.         if (p->sohn[right]->bal()<=d) lrot(p,father);
  686.         else ldrot(p,father);
  687.       else if (i>1-alpha) 
  688.              if (p->sohn[left]->bal() > d ) rrot(p,father);
  689.          else rdrot(p,father);
  690.     }
  691.   }
  692.  
  693.   if(empty(t))                      // delete item of end coordinate
  694.   {
  695.     sdel(x1);
  696.     if (!st.empty())                // father exists 
  697.     { q = st.pop();                 // pop father of leaf and set nodelist
  698.  
  699.       if (!st.empty())
  700.       { p = st.top();
  701.     if (cmp(key(q),key(p))<=0)  // left son deleted
  702.           p = p->sohn[left];
  703.         else                        // right son deleted
  704.       p = p->sohn[right];
  705.       } 
  706.       else                          // root deleted 
  707.     p = root;
  708.                                           // set nodelist
  709.       help = info(p);
  710.       info(p) = info(q);
  711.  
  712.       if (p->blatt())
  713.     forall_seg_tree_items(z,*help)
  714.       if ((start_coord(p,z))||(end_coord(p,z)))
  715.         info(p)->insert(r.key(z));
  716.  
  717.       delete help;
  718.       delete q;
  719.     }
  720.  
  721.     delete info(t);
  722.     delete t;
  723.  
  724.                                // rebalancieren
  725.     while (!st.empty())
  726.     { p=st.pop();
  727.       father = st.empty() ? 0 : st.top();
  728.       p->gr--;  
  729.       float i = p->bal();
  730.  
  731.       DDUMP("rebal cur=" << (int)key(p) << " groesse= " << p->groesse() << " bal= " << i << " in main tree \n");
  732.  
  733.       if (i < alpha)
  734.         if (p->sohn[right]->bal()<=d) lrot(p,father);
  735.         else ldrot(p,father);
  736.       else if (i>1-alpha) 
  737.              if (p->sohn[left]->bal() > d ) rrot(p,father);
  738.          else rdrot(p,father);
  739.     }
  740.   }
  741.  
  742. #ifdef DUMP
  743.   print_tree();
  744. #endif
  745.  
  746.  
  747.  
  748.   clear_dim1(x0);
  749.   clear_dim1(x1);
  750.   clear_dim2(y);
  751.   clear_info(inf(deleted));
  752.  
  753.   delete i;
  754.   delete deleted;
  755. }
  756.  
  757. //-------------------------------------------------------------------
  758. // query
  759. // returns all items it in the Segment_tree with
  760. //     x0(it) <= x <= x1(it) and y0 <= y(it) <= y1
  761. //    
  762. // by:
  763. // - look for x in the main tree   
  764. //   
  765. // - for all nodes on the path perform a query(y0,y1) on nodelists
  766.  
  767. list<seg_tree_item> Segment_Tree::query(GenPtr x, GenPtr y0, GenPtr y1)
  768.  
  769. { 
  770.   DPRINT("query in main tree " << (int)x << " " << (int)y0 << " " << (int)y1 << "\n");
  771.  
  772.   bb_item it;
  773.   seg_tree_item z;
  774.   list<seg_tree_item> L,l;
  775.  
  776.   search(x);
  777.   if (st.empty()) return L;
  778.  
  779.   if (cmp(x,key(st.top()))==0)             // x-coordinate in tree
  780.     while (!st.empty())
  781.     { it = st.pop();
  782.       l = info(it)->query(y0,y1);
  783.       L.conc(l);
  784.     }
  785.  
  786.   else                                     // x-coordinate not in tree
  787.   {
  788.      if ((cmp(x,key(bb_tree::min()))<0) || (cmp(x,key(bb_tree::max()))>0))
  789.        return L;
  790.    
  791.      list<seg_tree_item> L1;
  792.      while (!st.empty())
  793.      { it = st.pop();
  794.        L1 = info(it)->query(y0,y1);
  795.        forall(z,L1)
  796.      if ((cmp(x,x0(z))>=0) && (cmp(x,x1(z))<=0))
  797.        L.append(z);
  798.        L1.clear();
  799.      }
  800.   }
  801.  
  802.   return L;
  803. }
  804.  
  805. //-------------------------------------------------------------------
  806. // x_infinity_query
  807. // returns a List of all items it with y0 <= y0(it) <= y1
  808.  
  809. list<seg_tree_item> Segment_Tree::x_infinity_query(GenPtr y0, GenPtr y1)
  810. {
  811.   return r.query(y0,y1);
  812. }
  813.  
  814. //-------------------------------------------------------------------
  815. // y_infinity_query
  816. // returns a List of all items it with x0(it) <= x <= x1(it)
  817.  
  818. list<seg_tree_item> Segment_Tree::y_infinity_query(GenPtr x)
  819. {
  820.   bb_item it;
  821.   seg_tree_item z;
  822.   list<seg_tree_item> L;
  823.  
  824.   search(x);
  825.   if (st.empty()) return L;
  826.  
  827.   if (cmp(x,key(st.top()))==0)             // x-coordinate in tree
  828.     while (!st.empty())
  829.     { it = st.pop();
  830.       forall_seg_tree_items(z,*(info(it)))
  831.       L.append(z);
  832.     }
  833.  
  834.   else                                     // x-coordinate not in tree
  835.   {
  836.      if ((cmp(x,key(bb_tree::min()))<0) || (cmp(x,key(bb_tree::max()))>0))
  837.        return L;
  838.    
  839.      list<seg_tree_item> L1;
  840.      while (!st.empty())
  841.      { it = st.pop();
  842.        forall_seg_tree_items(z,*(info(it)))
  843.      if ((cmp(x,x0(z))>=0) && (cmp(x,x1(z))<=0))
  844.        L.append(z);
  845.      }
  846.   }
  847.  
  848.   return L;
  849. }
  850.  
  851.  
  852. //-------------------------------------------------------------------
  853. // all_items
  854. // returns all items in the tree
  855.  
  856. list<seg_tree_item> Segment_Tree::all_items()
  857. {
  858.   return r.all_items();
  859. }
  860.  
  861.  
  862. //-------------------------------------------------------------------
  863. // lookup
  864. // returns a seg_tree_item it with key(it) = (x0,x1,y) if there is one
  865.  
  866. seg_tree_item Segment_Tree::lookup(GenPtr x0, GenPtr x1, GenPtr y)
  867. { 
  868.   DPRINT(" lookup in main tree " << (int)x0 << " " << (int)x1 << " " << (int)y << "\n");
  869.   h_segment_p z = new h_segment(x0,x1,y);
  870.   seg_tree_item i = r.lookup(z);   
  871.   delete z;
  872.   return i;
  873. }
  874.  
  875.  
  876. //-------------------------------------------------------------------
  877. // clear_tree
  878. // delete all Items and Tree of Items
  879.  
  880. void Segment_Tree::clear_tree()
  881. {
  882.   if (!root) return;
  883.  
  884.   clear(root);
  885.  
  886.   seg_tree_item z;
  887.   h_segment_p q;
  888.  
  889.   forall_seg_tree_items(z,r)
  890.   { 
  891.     q=r.key(z);
  892.     clear_dim1(x0(q));
  893.     clear_dim1(x1(q));
  894.     clear_dim2(y(q));
  895.     clear_info(inf(q));
  896.     delete q;
  897.   }
  898.   r.clear();
  899.  
  900.   first = iterator = 0;
  901.   anzahl = 0;
  902. }
  903.  
  904. //-------------------------------------------------------------------
  905. // clear
  906. // delete nodelists and nodes
  907.  
  908.  
  909. void Segment_Tree::clear(bb_item& it)
  910. {
  911.   if (it == 0) return;
  912.   
  913.   if(!it->blatt())
  914.   { clear(it->sohn[left]);
  915.     clear(it->sohn[right]);
  916.   }
  917.  
  918.   delete info(it);
  919.   delete it;
  920.   it = 0;
  921.  
  922. }
  923.  
  924. //-------------------------------------------------------------------
  925. // print     
  926. // prints the tree with nodelists
  927.  
  928. void Segment_Tree::print(bb_item it,string s)
  929. {
  930.   if (!it) return;
  931.  
  932.   seg_tree_item i;
  933.  
  934.   if (!it->blatt())
  935.     print(it->sohn[left],s+"     ");
  936.  
  937.   cout<< s << (int)key(it) <<"\n";
  938.   cout<< s ; 
  939.   forall_seg_tree_items(i,*info(it))
  940.     cout << "[" << (int)r.key(i) << "]:" << *(r.key(i)) << " ";
  941.   newline;
  942.  
  943.   if (!it->blatt())
  944.     print(it->sohn[right],s+"     ");
  945. }
  946.  
  947.